import java.util.*;

public class Solution {
    private class Orange {
        public int x, y, times;

        public Orange(int x, int y) {
            this.x = x;
            this.y = y;
            this.times = 0;
        }

        public Orange(int x, int y, int times) {
            this.x = x;
            this.y = y;
            this.times = times;
        }
    }

    public int orangesRotting(int[][] grid) {
        Queue<Orange> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) queue.add(new Orange(i, j));
            }
        }
        int maxtimes = 0;
        while (!queue.isEmpty()) {
            Orange c = queue.poll();
            maxtimes = Math.max(c.times, maxtimes);
            int[] dx = {-1, 0, 1, 0};
            int[] dy = {0, -1, 0, 1};
            for (int i = 0; i < 4; i++) {
                int nx = c.x + dx[i], ny = c.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) continue;
                if (grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    queue.add(new Orange(nx, ny, c.times + 1));
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }
        return maxtimes;
    }
}